#include "util.h"
#include "common_sort.h"
#include <deque>


void IterativeQuickSort::sort(std::vector<int>& vec) {
	if (vec.size() <= 1) {
		return;
	}

	std::deque<int> dq;

	dq.push_back(0);
	dq.push_back(vec.size() - 1);

	while (!dq.empty()) {
		int start = dq.front();
		dq.pop_front();
		int end = dq.front();
		dq.pop_front();

		int pi = partition(vec, start, end);
		if (pi - 1 > start) {
			dq.push_back(start);
			dq.push_back(pi - 1);
		}

		if (pi + 1 < end) {
			dq.push_back(pi + 1);
			dq.push_back(end);
		}
	}
}

int IterativeQuickSort::partition(std::vector<int>& vec, int start, int end) {
	int pivot = vec[end];
	int i = start - 1;

	for (int j = start; j <= end - 1; ++j) {
		if (vec[j] <= pivot) {
			++i;
			util::swap(vec, i, j);
		}
	}

	util::swap(vec, i + 1, end);

	return i + 1;
}

